//
//  Problem62.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 62. 不同路径
 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 问总共有多少条不同的路径？

 示例 1：
     输入：m = 3, n = 7
     输出：28
 示例 2：
     输入：m = 3, n = 2
     输出：3
     解释：
     从左上角开始，总共有 3 条路径可以到达右下角。
     1. 向右 -> 向下 -> 向下
     2. 向下 -> 向下 -> 向右
     3. 向下 -> 向右 -> 向下
 示例 3：
     输入：m = 7, n = 3
     输出：28
 示例 4：
     输入：m = 3, n = 3
     输出：6
 提示：
     1 <= m, n <= 100
     题目数据保证答案小于等于 2 * 109
 */
@objcMembers class Problem62: NSObject {
    func solution() {
        print(uniquePathsClearAlloc(3, 7))
        print(uniquePathsClearAlloc(3, 2))
    }
    
    /*
     动态规划
     1: 创建一个二位数组dp[m][n]
     2: dp[i][j]导致右下角的路径个数
     3: dp[i][j] = dp[i+1][j](向下) + dp[i][j+1](向右)
     */
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        if m == 1, n == 1 {
            return 1
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        dp[m-1][n-1] = 1
        let value = uniquePathsDP(&dp, 0, 0)
        for i in 0..<dp.count {
            print(dp[i])
        }
        return value
    }
    
    func uniquePathsDP(_ dp: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i >= dp.count || j >= dp[0].count {      // 边界
            return 0
        }
        if dp[i][j] != 0 {
            return dp[i][j]
        }
        
        dp[i][j] = uniquePathsDP(&dp, i+1, j)  + uniquePathsDP(&dp, i, j+1)
        return dp[i][j]
    }
    
    /*
     不是用递归的方法
     */
    func uniquePaths1(_ m: Int, _ n: Int) -> Int {
        if m == 1, n == 1 {
            return 1
        }
        
        var dp = Array(repeating: Array(repeating: 1, count: n), count: m)
        
        var i = m - 2
        while i >= 0 {
            var j = n-2
            while j >= 0 {
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
                j -= 1
            }
            i -= 1
        }
        
        return dp[0][0]
    }
    
    /*
     不是用递归的方法 优化空间：
     dp[i][j] = dp[i+1][j] + dp[i][j+1]
     dp[i][j] 只与 dp[i+1][j] 和 dp[i][j+1] 有关
     分析 dp[i][j+1] 其实就是上一个数 => +=
     分析 dp[i+1][j] 那就创建一个数组，每次记录他
     简化成数组，dp[n]
     */
    func uniquePathsClearAlloc(_ m: Int, _ n: Int) -> Int {
        if m == 1, n == 1 {
            return 1
        }
        
        var dp = Array(repeating: 1, count: n)
        
        var i = m - 2
        while i >= 0 {
            var j = n-2
            while j >= 0 {
                dp[j] += dp[j+1]
                j -= 1
            }
            i -= 1
        }
        
        return dp[0]
    }
}
